/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package app.OtherWeightedFPTree;

import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 *
 * @author Kumori
 */
public class FPgrowth extends FrequentItemsetsMiner {
    private DBReader db_reader;
    private DBCacheWriter cache_writer;
    
  private static class FPTreeNode 
  {
    // data
    int item;           // item id
    int count;          // item count

    int seq_num;        // sequence number of node, = (depth + 1)
    int header_index;   // index in header of the entry for item

    // links
    FPTreeNode parent;  // parent node
    FPTreeNode child;   // first child node
    FPTreeNode sibling; // next sibling node
    FPTreeNode next;    // next node in FPTree containing same item 

    FPTreeNode()
    {
    }

    FPTreeNode(int i, int c, int sn, int hi,
	       FPTreeNode p, FPTreeNode s, FPTreeNode n)
    {
      item = i;
      count = c;
      seq_num = sn;
      header_index = hi;
      parent = p;
      sibling = s;
      next = n;
    }
  }

  private static class FPTreeHeaderEntry
  {
    int item;
    int count; 
    FPTreeNode head;

    FPTreeHeaderEntry()
    {
      }

    FPTreeHeaderEntry(int i)
    {      item = i;
    }
  }

  private class FPTree
  {
    FPTreeHeaderEntry[] header;
    FPTreeNode root;
    Map item2index;
    boolean hasMultiplePaths;
    int count_nodes;
    long num_rows;
    long min_weight;
    DBCacheWriter cache_writer;

    FPTree(int[] items, long num_rows, long min_weight,
	   DBCacheWriter cache_writer)
    {
      header = new FPTreeHeaderEntry[items.length];
      root = new FPTreeNode();
      item2index = new HashMap(items.length);
      this.num_rows = num_rows;
      this.min_weight = min_weight;
      this.cache_writer = cache_writer;

      for (int i = 0; i < items.length; i++)
	{
	  header[i] = new FPTreeHeaderEntry(items[i]);
	  item2index.put(new Integer(items[i]), new Integer(i));
	}
    }
    void insert(int[] items, int count)
    {
      FPTreeNode current_node = root; 
      for (int index = 0; index < items.length; index++)
	{
	  int entry_index 
	    = ((Integer)item2index.get(new Integer(items[index]))).intValue();
	  header[entry_index].count += count;
	  FPTreeNode walker = current_node.child;
	  for ( ; walker != null; walker = walker.sibling)
	    if (walker.item == items[index])
	      break;
	  if (walker == null)
	    {
	      if (current_node.child != null)
		hasMultiplePaths = true;
	     count_nodes++;
	      FPTreeNode new_node = new FPTreeNode(items[index], count,
						   index + 1, entry_index,
						   current_node, 
						   current_node.child, 
						   header[entry_index].head);
	      header[entry_index].head = new_node;
	      current_node.child = new_node;
	      current_node = new_node;
	    }
	  else
	    {
	      walker.count += count;
	      current_node = walker;
	    }
	}
    }

    void fp_growth(Itemset is_suffix)
    {
      checkAbort();
      if (!hasMultiplePaths)
	{
	  int[] items = new int[header.length];
	  for (int i = 0; i < header.length; i++)
	    items[header.length - i - 1] = header[i].item;
	  combine(items, is_suffix);
	}
      else
	for (int i = header.length - 1; i >= 0; i--)
	  {
	    Itemset is_new = new Itemset(is_suffix);
	    is_new.add(header[i].item);
	    is_new.setWeight(header[i].count);
	    is_new.setSupport((double)header[i].count / (double)num_rows);
	    try
	      {
		if (cache_writer != null)
		  cache_writer.writeItemset(is_new);
	      }
	    catch (IOException e)
	      {
		System.err.println("Error writing cache!!!\n" + e);
	      }
	    FPTree fpt = buildConditionalFPTree(header[i].item);
	    if (fpt != null)
	      fpt.fp_growth(is_new);
	  }
    }
    void combine(int[] items, Itemset is_combination)
    {
      int count;
      for (int i = 0; i < items.length; i++)
	{
	  Itemset is_new_combination = new Itemset(is_combination);
	  is_new_combination.add(items[i]);
	  count = header[header.length - i - 1].count;
	  is_new_combination.setWeight(count);
	  is_new_combination.setSupport((double)count / (double)num_rows);
	  try
	    {
	      if (cache_writer != null)
		cache_writer.writeItemset(is_new_combination);
	    }
	  catch (IOException e)
	    {
	      System.err.println("Error writing cache!!!\n" + e);
	    }
	  combine(items, is_new_combination, i + 1);
	}
    }

    void combine(int[] items, Itemset is_combination, int from)
    {
      for (int i = from; i < items.length; i++)
	{
	  Itemset is_new_combination = new Itemset(is_combination);
	  is_new_combination.add(items[i]);
	  try
	    {
	      if (cache_writer != null)
		cache_writer.writeItemset(is_new_combination);
	    }
	  catch (IOException e)
	    {
	      System.err.println("Error writing cache!!!\n" + e);
	    }
	  combine(items, is_new_combination, i + 1);
	}
    }

    FPTree buildConditionalFPTree(int item)
    {
      int entry_index 
	= ((Integer)item2index.get(new Integer(item))).intValue();
      int[] counts = new int[entry_index];
      for (FPTreeNode side_walker = header[entry_index].head;
	   side_walker != null; side_walker = side_walker.next)
	for (FPTreeNode up_walker = side_walker.parent;
	     up_walker != root; up_walker = up_walker.parent)
	  counts[up_walker.header_index] += side_walker.count;
      int num_frequent = 0;
      for (int i = 0; i < counts.length; i++)
	if (counts[i] >= min_weight)
	  num_frequent++;
         if (num_frequent == 0)
	return null;
      Item[] item_objs = new Item[num_frequent];
      for (int i = 0, j = 0; i < counts.length; i++)
	if (counts[i] >= min_weight)
	  item_objs[j++] = new Item(header[i].item, counts[i]);
      Arrays.sort(item_objs);
            int[] items = new int[num_frequent];
      for (int i = 0; i < num_frequent; i++)
	items[i] = item_objs[num_frequent - i - 1].item;
      
      FPTree fpt = new FPTree(items, num_rows, min_weight, cache_writer);

      for (FPTreeNode side_walker = header[entry_index].head;
	   side_walker != null; side_walker = side_walker.next)
	if (side_walker.parent != root)
	  {
	    int i = side_walker.parent.seq_num;
	    Item[] pattern = new Item[i];
	    for (FPTreeNode up_walker = side_walker.parent;
		 up_walker != root; up_walker = up_walker.parent)
	      pattern[--i] = new Item(up_walker.item, up_walker.header_index);

	    processPattern(pattern, side_walker.count, fpt, counts);
	  }

      return fpt;
    }
    void processPattern(Item[] pattern, int count, FPTree fpt,
			int[] counts)
    {
      int i, j, num_frequent;
      Item item_obj;
      int[] items;
      Item[] item_objs;

      for (i = 0, num_frequent = 0; i < pattern.length; i++)
	{
	  item_obj = pattern[i];
	  if (counts[item_obj.count] >= min_weight)
	    num_frequent++;
	}
	    
      if (num_frequent > 0)
	{
	  item_objs = new Item[num_frequent];
	  for (i = 0, j = 0; i < pattern.length; i++)
	    {
	      item_obj = pattern[i];
	      if (counts[item_obj.count] >= min_weight)
		item_objs[j++] = new Item(item_obj.item, 
					  counts[item_obj.count]);
	    }
	
	  Arrays.sort(item_objs);
	
	  items = new int[num_frequent];
	  for (i = 0; i < num_frequent; i++)
	    items[i] = item_objs[num_frequent - i - 1].item;

	  fpt.insert(items, count);
	}
    }
  }

  private static class Item implements Comparable
  {
    int item;
    int count;

    Item(int i, int c)
    {
      item = i;
      count = c;
    }

    @Override
	public int compareTo(Object o)
    {
      Item other = (Item)o;
      return (count - other.count);
    }

    @Override
	public String toString()
    {
      return "<" + item + ", " + count + ">";
    }
  }

  private long num_rows;
  private int num_cols;
  private long min_weight;
  private int[] counts;
  private int pass_num;
  public int findFrequentItemsets(DBReader dbReader, 
				  DBCacheWriter cacheWriter,
				  double minSupport)
  {
    db_reader = dbReader;
    cache_writer = cacheWriter;
    num_rows = dbReader.getNumRows();
    num_cols = (int)db_reader.getNumColumns(); 
    min_weight = (long)(num_rows * minSupport);

    checkAbort();

    countItemOccurrences();

    checkAbort();
    FPTree fpt = constructFPTree();
   
    if (fpt != null)
      {
	System.out.println("<FPgrowth>: FPTree has " + fpt.count_nodes 
			   + " nodes");
	fpt.fp_growth(new Itemset());
      }
    else
      System.out.println("<FPgrowth>: FPTree is empty");
      
    return pass_num;
  }
  private void countItemOccurrences()
  {
    counts = new int[num_cols + 1];
    try
      {
	Itemset row = db_reader.getFirstRow();
	for (int i = 0; i < row.size(); i++)
	 counts[row.get(i)]++;
	while (db_reader.hasMoreRows())
	  {
	    row = db_reader.getNextRow();
	    for (int i = 0; i < row.size(); i++)
	      counts[row.get(i)]++;
	  }
      }
    catch (Exception e)
      {
	System.err.println("Error scanning database!!!\n" + e);
      }
        pass_num++;
  }

  private FPTree constructFPTree()
  {
    int num_frequent = 0;
    for (int i = 1; i < counts.length; i++)
      if (counts[i] >= min_weight)
	num_frequent++;
    if (num_frequent == 0)
      return null;
    // put all frequent items in an array of Items
    Item[] item_objs = new Item[num_frequent];
    for (int i = 1, j = 0; i < counts.length; i++)
      if (counts[i] >= min_weight)
	item_objs[j++] = new Item(i, counts[i]);
    // and sort them ascendingly according to weight
    Arrays.sort(item_objs);

    // then place the items in an array of ints in descending order
    int[] items = new int[num_frequent];
    for (int i = 0; i < num_frequent; i++)
      items[i] = item_objs[num_frequent - i - 1].item;

    // initialize FPTree
    FPTree fpt = new FPTree(items, num_rows, min_weight, cache_writer);
    try
      {	Itemset row = db_reader.getFirstRow();
	processRow(row, fpt);
	while (db_reader.hasMoreRows())
	  {    row = db_reader.getNextRow();
	    processRow(row, fpt);
	  }
      }
    catch (Exception e)
      {
	System.err.println("Error scanning database!!!\n" + e);
      }
    pass_num++;
    return fpt;
  }
  private void processRow(Itemset row, FPTree fpt)
  {
    int i, j, item, num_frequent;
    int[] items;
    Item[] item_objs;
    for (i = 0, num_frequent = 0; i < row.size(); i++)
      {
	item = row.get(i);
	if (counts[item] >= min_weight)
	  num_frequent++;
      }
	   
    if (num_frequent > 0)
      {	item_objs = new Item[num_frequent];
	for (i = 0, j = 0; i < row.size(); i++)
	  {
	    item = row.get(i);
	    if (counts[item] >= min_weight)
	      {
		item_objs[j++] = new Item(item, counts[item]);
	      }
	  }
		Arrays.sort(item_objs);
		items = new int[num_frequent];
	for (i = 0; i < num_frequent; i++)
	  items[i] = item_objs[num_frequent - i - 1].item;
	fpt.insert(items, 1);
      }
  }
}

